package algorithm;

import java.util.ArrayList;
import java.util.Collections;
public class merge_sort_arraylist {


		public static int num = 19;
		public static ArrayList<Integer> list = new ArrayList<Integer> (num);
		
		
		public static void main(String[] args) 
		{

			for (int i = 0; i < num; i++)
				
			{
				list.add(i);
			}
			Collections.shuffle(list);
			System.out.println(list);

			list = mergesort(list);
			System.out.println(list);
		}	
		
		public static ArrayList<Integer> mergesort(ArrayList<Integer> m)
		{
			int lol=m.size();
			ArrayList<Integer> left = new ArrayList<Integer> (lol/2), right=new ArrayList<Integer> (lol/2), result=new ArrayList<Integer> (lol);
		    if (m.size() <= 1)
		        return m;
		    else
		    {
			        int middle = m.size() / 2;
			        for(int i = 0 ; i < middle;i++)
			        {
			        	left.add(m.get(i));
			        }
			        System.out.println(left);
			        for(int i= middle; i< m.size();i++)
			        {
			        	right.add(m.get(i));
			        }
			        System.out.println(right);
			        left = mergesort(left);
			        right = mergesort(right);
			        result = merge(left, right);
			        return result;
		    }
		}
		public static ArrayList<Integer> merge(ArrayList<Integer> left,ArrayList<Integer> right)
		{
			ArrayList<Integer>  result=new ArrayList<Integer> (left.size()+right.size());
			int ind=0;
		    while (left.size() > 0 && right.size() > 0)
		    {
		        if (left.get(0) <= right.get(0))
		        {
		            result.add(ind, left.get(0));
		            left.remove(0);
		            ind++;
		        }
		        else
		        {
		            result.add(ind, right.get(0));
		            right.remove(0);
		            ind++;
		        }
		    }
		    if (left.size() > 0)
		    	result.addAll(ind, left);
		    if (right.size() > 0)
		    	result.addAll(ind, right);
		    return result;
		}

}
